package me.qingy.old.binary_search;

/**
 * @author qingy
 * @since 2021/1/29
 */
public class SearchMatrix {
    /**
     * 依题可得二维数组展开即为适用于二分查找的顺序表
     * 相较于一位数组，只不过mid元素的获取不那么直接而已
     * 展开成一位数组的mid下标：idx = row * n + col
     * row = idx / n
     * col = ids % n
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;

        int l = 0;
        int r = m * n - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            int midElement = matrix[mid / n][mid % n];

            if (target > midElement)
                l = mid + 1;
            else if (target < midElement)
                r = mid - 1;
            else
                return true;
        }

        return false;
    }
}
